package pers.qianyu.month_202011.date_20201120;

import java.util.*;

/**
 * 106. 从中序与后序遍历序列构造二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 *
 * @author mizzle rain
 * @date 2020-11-20 21:59
 */
public class BuildTreeTwo {
    private HashMap<Integer, Integer> map = new HashMap<>();
    private int[] postorder;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) {
            return null;
        }
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        this.postorder = postorder;
        return recur(0, postorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode recur(int postLeft, int postRight, int inLeft, int inRight) {
        if (postLeft > postRight || inLeft > inRight) {
            return null;
        }
        int nodeValue = postorder[postRight];
        Integer midIndex = map.get(nodeValue);
        TreeNode node = new TreeNode(nodeValue);
        int leftSpace = midIndex - inLeft;
        int rightSpace = inRight - midIndex;
        node.left = recur(postLeft, postRight - 1 - rightSpace,
                inLeft, midIndex - 1);
        node.right = recur(postLeft + leftSpace, postRight - 1,
                midIndex + 1, inRight);
        return node;
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
